刷題：75. Sort Colors

題目

連結

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Follow up:

• Could you solve this problem without using the library's sort function?
• Could you come up with a one-pass algorithm using only O(1) constant space?

Example 1:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Example 2:

Input: nums = [2,0,1]
Output: [0,1,2]

Constraints

n == nums.length
1 <= n <= 300
nums[i] is 0, 1, or 2.

思考

這題其實是很單純的 Sort 問題，基本上六種 Sort 都可以解決。

解題

JS

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
const sortColors = function (nums) {
  /* 以下六選一 */
  bubbleSort(nums);
  selectionSort(nums);
  insertionSort(nums);
  heapSort(nums);
  mergeSort(nums, 0, nums.length - 1);
  quickSort(nums, 0, nums.length - 1);
};

/**
 * @param {number[]} data
 * @param {number} i
 * @param {number} j
 */
const swap = (data, i, j) => {
  const temp = data[i];
  data[i] = data[j];
  data[j] = temp;
}

/**
 * Bubble Sort
 * @param {number[]} nums
 */
const bubbleSort = (nums) => {
  const n = nums.length;

  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      if (nums[j] > nums[j + 1]) {
        swap(nums[j], nums[j + 1]);
      }
    }
  }
}

/**
 * @param {number[]} nums
 */
const selectionSort = (nums) => {
  for (let i = 0; i < nums.length; i++) {
    let minIndex = i;

    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] < nums[minIndex]) {
        minIndex = j;
      }
    }

    swap(nums, minIndex, i);
  }
};

/**

 * @param {number[]} nums
 */
const insertionSort = (nums) => {
  for (let i = 0; i < nums.length; i++) {
    let key = nums[i];
    let j = i - 1;

    while (j >= 0 && nums[j] > key) {
      nums[j + 1] = nums[j];
      j--;
    }

    nums[j + 1] = key;
  }
};

/**
 * @param {number[]} nums
 * @param {number} heapSize
 * @param {number} index
 */
const heapify = (nums, heapSize, index) => {
  let largest = index, left = 2 * index + 1, right = 2 * index + 2;

  if (left < heapSize && nums[left] > nums[largest]) {
    largest = left;
  }

  if (right < heapSize && nums[right] > nums[largest]) {
    largest = right;
  }

  if (largest !== index) {
    let temp = nums[index];
    nums[index] = nums[largest];
    nums[largest] = temp;

    heapify(nums, heapSize, largest);
  }
};

/**
 * @param {number[]} nums
 */
const heapSort = (nums) => {
  const n = nums.length;

  for (let i = (n >> 1) - 1; i >= 0; i--) {
    heapify(nums, n, i);
  }

  for (let i = n - 1; i > 0; i--) {
    let temp = nums[0];
    nums[0] = nums[i];
    nums[i] = temp;

    heapify(nums, i, 0);
  }
};

const merge = (nums, l, m, n) => {
  const n1 = m - l + 1;
  const n2 = n - m;

  let L = new Array(n1);
  let R = new Array(n2);

  for (let i = 0; i < n1; i++) {
    L[i] = nums[l + i];
  }

  for (let j = 0; j < n2; j++) {
    R[j] = nums[m + 1 + j];
  }

  let i = 0, j = 0;
  let k = l;

  while (i < n1 && j < n2) {
    if (L[i] <= R[j]) {
      nums[k] = L[i];
      i++;
    } else {
      nums[k] = R[j];
      j++;
    }

    k++;
  }

  while (i < n1) {
    nums[k] = L[i];
    i++;
    k++;
  }

  while (j < n2) {
    nums[k] = R[j];
    j++;
    k++;
  }
};

const mergeSort = (nums, l, n) => {
  if (l < n) {
    let m = (l + n) >> 1;

    mergeSort(nums, l, m);
    mergeSort(nums, m + 1, n);

    merge(nums, l, m, n);
  }
}

/**
 * @param {number[]} nums
 * @param {number} low
 * @param {number} high
 */
const partition = (nums, low, high) => {
  let pivot = nums[high];
  let i = (low - 1);

  for (let j = low; j < high; j++) {
    if (nums[j] < pivot) {
      i++;
      let temp = nums[i];
      nums[i] = nums[j];
      nums[j] = temp;
    }
  }

  let temp = nums[i + 1];
  nums[i + 1] = nums[high];
  nums[high] = temp;
  return (i + 1);
};

/**
 * @param {number[]} nums
 * @param {number} low
 * @param {number} high
 */
const quickSort = (nums, low, high) => {
  if (low < high) {
    let pi = partition(nums, low, high);

    quickSort(nums, low, pi - 1);
    quickSort(nums, pi + 1, high);
  }
};

Java

class Solution {
    public void sortColors(int[] nums) {
        /* 以下六選一 */
        bubbleSort(nums);
        selectionSort(nums);
        insertionSort(nums);
        mergeSort(nums, 0, nums.length - 1);
        quickSort(nums, 0, nums.length - 1);
    }

    public void swap(int[] data, int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    public void bubbleSort(int[] nums) {
        int n = nums.length;

        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                }
            }
        }
    }

    public void selectionSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int minIndex = i;

            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[minIndex]) {
                    minIndex = j;
                }
            }

            swap(nums, minIndex, i);
        }
    }

    public void insertionSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int key = nums[i];
            int j = i - 1;

            while (j >= 0 && nums[j] > key) {
                nums[j + 1] = nums[j];
                j--;
            }

            nums[j + 1] = key;
        }
    }

    void heapify(int nums[], int heapSize, int index) {
        int largest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;

        if (left < heapSize && nums[left] > nums[largest]) {
            largest = left;
        }

        if (right < heapSize && nums[right] > nums[largest]) {
            largest = right;
        }

        if (largest != index) {
            int temp = nums[index];
            nums[index] = nums[largest];
            nums[largest] = temp;

            heapify(nums, heapSize, largest);
        }
    }

    public void heapSort(int nums[]) {
        int n = nums.length;

        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(nums, n, i);
        }

        for (int i = n - 1; i > 0; i--) {
            int temp = nums[0];
            nums[0] = nums[i];
            nums[i] = temp;

            heapify(nums, i, 0);
        }
    }

    public void merge(int[] nums, int l, int m, int n) {
        int n1 = m - l + 1;
        int n2 = n - m;

        int L[] = new int[n1];
        int R[] = new int[n2];

        for (int i = 0; i < n1; i++) {
            L[i] = nums[l + i];
        }

        for (int j = 0; j < n2; j++) {
            R[j] = nums[m + 1 + j];
        }

        int i = 0, j = 0;
        int k = l;

        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                nums[k] = L[i];
                i++;
            } else {
                nums[k] = R[j];
                j++;
            }

            k++;
        }

        while (i < n1) {
            nums[k] = L[i];
            i++;
            k++;
        }

        while (j < n2) {
            nums[k] = R[j];
            j++;
            k++;
        }
    }

    public void mergeSort(int[] nums, int l, int n) {
        if (l < n) {
            int m = (l + n) / 2;
            mergeSort(nums, l, m);
            mergeSort(nums, m + 1, n);

            merge(nums, l, m, n);
        }
    }

    public int partition(int nums[], int low, int high) {
        int pivot = nums[high];
        int i = (low - 1);

        for (int j = low; j < high; j++) {
            if (nums[j] < pivot) {
                i++;
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }

        int temp = nums[i + 1];
        nums[i + 1] = nums[high];
        nums[high] = temp;
        return (i + 1);
    }

    public void quickSort(int nums[], int low, int high) {
        if (low < high) {
            int pi = partition(nums, low, high);

            quickSort(nums, low, pi - 1);
            quickSort(nums, pi + 1, high);
        }
    }
}

C

void solution1(int *nums, int numsSize);
void solution2(int *nums, int numsSize);
void swap(int *nums, int i, int j);
void bubbleSort(int *nums, int numsSize);
void selectionSort(int *nums, int numsSize);
void insertionSort(int *nums, int numsSize);
void heapify(int nums[], int heapSize, int index);
void heapSort(int nums[], int numsSize);
void merge(int *nums, int l, int m, int n);
void mergeSort(int *nums, int l, int n);
int partition(int *nums, int low, int high);
void quickSort(int *nums, int low, int high);

void sortColors(int *nums, int numsSize)
{
    /* 以下六選一 */
    bubbleSort(nums, numsSize);
    selectionSort(nums, numsSize);
    insertionSort(nums, numsSize);
    heapSort(nums, numsSize);
    mergeSort(nums, 0, numsSize - 1);
    quickSort(nums, 0, numsSize - 1);
};

void swap(int *nums, int i, int j)
{
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

void bubbleSort(int *nums, int numsSize)
{
    int i, j;

    for (i = 0; i < numsSize - 1; i++)
    {
        for (j = 0; j < numsSize - i - 1; j++)
        {
            if (nums[j] > nums[j + 1])
            {
                swap(nums, j, j + 1);
            }
        }
    }
}

void selectionSort(int *nums, int numsSize)
{
    int i, j;

    for (i = 0; i < numsSize; i++)
    {
        int minIndex = i;

        for (j = i + 1; j < numsSize; j++)
        {
            if (nums[j] < nums[minIndex])
            {
                minIndex = j;
            }
        }

        swap(nums, minIndex, i);
    }
}

void insertionSort(int *nums, int numsSize)
{
    int i;

    for (i = 0; i < numsSize; i++)
    {
        int key = nums[i];
        int j = i - 1;

        while (j >= 0 && nums[j] > key)
        {
            nums[j + 1] = nums[j];
            j--;
        }

        nums[j + 1] = key;
    }
}

void heapify(int nums[], int heapSize, int index)
{
    int largest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;

    if (left < heapSize && nums[left] > nums[largest])
    {
        largest = left;
    }

    if (right < heapSize && nums[right] > nums[largest])
    {
        largest = right;
    }

    if (largest != index)
    {
        swap(nums, index, largest);
        heapify(nums, heapSize, largest);
    }
}

void heapSort(int nums[], int numsSize)
{
    for (int i = numsSize / 2 - 1; i >= 0; i--)
    {
        heapify(nums, numsSize, i);
    }

    for (int i = numsSize - 1; i > 0; i--)
    {
        swap(nums, 0, i);
        heapify(nums, i, 0);
    }
}

void merge(int *nums, int l, int m, int n)
{
    int i, j;
    int n1 = m - l + 1;
    int n2 = n - m;

    int L[n1], R[n2];

    for (i = 0; i < n1; i++)
    {
        L[i] = nums[l + i];
    }

    for (j = 0; j < n2; j++)
    {
        R[j] = nums[m + 1 + j];
    }

    i = 0, j = 0;
    int k = l;

    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            nums[k] = L[i];
            i++;
        }
        else
        {
            nums[k] = R[j];
            j++;
        }

        k++;
    }

    while (i < n1)
    {
        nums[k] = L[i];
        i++;
        k++;
    }

    while (j < n2)
    {
        nums[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int *nums, int l, int n)
{
    if (l < n)
    {
        int m = l + (n - l) / 2;
        mergeSort(nums, l, m);
        mergeSort(nums, m + 1, n);

        merge(nums, l, m, n);
    }
}

int partition(int *nums, int low, int high)
{
    int pivot = nums[high];
    int i = (low - 1);

    for (int j = low; j < high; j++)
    {
        if (nums[j] < pivot)
        {
            i++;
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }

    int temp = nums[i + 1];
    nums[i + 1] = nums[high];
    nums[high] = temp;
    return (i + 1);
}

void quickSort(int *nums, int low, int high)
{
    if (low < high)
    {
        int pi = partition(nums, low, high);

        quickSort(nums, low, pi - 1);
        quickSort(nums, pi + 1, high);
    }
}

看法

基本上這六種已經足夠應付了。倒是 Related Topics 與 Follow Up 暗示除了正規的 Sort 做法外，有取巧的做法。有興趣的人請去看這篇，大意就是用三個指針對陣列進行操作，說實在的，佩服能想出這個解法的天才！

結論

這六種是 Sort 最基本的應用，也可以說是常見的考題。單純看程式碼的數量，不能發現越複雜的 Sort，時間複雜度是較低的（O(n^2) vs O(n log n)）。這其實回到開發的本質，大部分都是先求有再求好，可能用內建的 Array.sort() 函式，或是寫個 Bubble Sort 來支援需求。等到之後有時間再找尋適合的 Sort 好增進效率。